package katas.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class MagicSquare {
	int size;
	int constant;
	
	public MagicSquare(int n) {
		size = (int)Math.sqrt(n);
		constant = ((int)Math.pow(size, 3) + size) / 2;
	}
	
	private boolean checkAnswer(Integer[] square){
		
		//check row sums
		for (int i = 0; i < square.length; i+=size) {
			int sum = 0;
			for (int j = i; j < i+size; j++) {
				sum += square[j];
			}
			if(sum != constant) return false;
		}
		
		//check column sums
		for (int i = 0; i < size; i++) {
			int sum = 0;
			for (int j = i; j < square.length; j+=size) {
				sum += square[j];
			}
			if(sum != constant) return false;
		}
		
		//check first diagonal sum
		int sum = 0;
		for (int i = 0; i < square.length; i+=size+1) 
			sum += square[i];
		if(sum != constant) return false;
		
		//check second diagonal sum
		sum = 0;
		for (int i = size-1; i < square.length-1; i+=size-1) 
			sum += square[i];
		if(sum != constant) return false;
		
		//all tests passed
		return true;
	}
	
	/**
	 * Find solution to the magic square of size 0
	 */
	private void solveSquare(Integer[] square, boolean[] used, int i, List<Integer[]> solutions){
		if(i == square.length){
			if(checkAnswer(square))
				solutions.add(square.clone());
		}
		else{
			for (int num = 1; num <= square.length; num++) {
				square[i] = num;
				
				if(used[num] == false){
					//check if row sums to magic
					if( (i+1) % size == 0){ 
						int sum = 0;
						for (int j = i-size+1; j <= i; j++)
							sum += square[j];
						if(sum != constant) continue;
					}
					used[num] = true;
				}
				else
					continue;
				
				solveSquare(square, used, i+1, solutions);
				used[num] = false;
			}
		}
	}
	
	public static void main(String[] args) {
		MagicSquare ms = new MagicSquare(9);
		
		List<Integer[]> solutions = new LinkedList<Integer[]>();
		long timeNow = System.currentTimeMillis();
		ms.solveSquare(new Integer[9], new boolean[10], 0, solutions);
		System.out.println("Found " + solutions.size() + " solutions in " + (System.currentTimeMillis() - timeNow) + "ms. ");
		for(Integer[] square : solutions){
			for (int i = 0; i < square.length; i++)
				System.out.print(square[i] + " ");
			System.out.println();
		}
	}
}
